The invention relates generally to address generation and more particular to address generation for a memory having a total number of storage locations not equal to a power of 2.
Generally, memory banks include 2.sup.n storage locations, where n is an integer. Examples include 8K (or 8.times.1024), 16K, 64K, and 128K memory units. The memory cells can then be accessed utilizing n-bit binary addresses.
In many systems the memory is divided into a large main memory consisting of slow inexpensive hardware and small cache memory consisting of high speed expensive hardware. Systems are designed to move the data in main memory most likely to be used by a program into the cache.
In a typical cache memory system, the main memory is made up of 2.sup.M blocks, each 2.sup.B bytes in size. The cache consists of 2.sup.N cache entries, each entry holding one memory block. Because N is much less than M, the system must map multiple main memory blocks to individual cache entries. In order to differentiate which particular memory block resides in a cache entry at a given time, each cache entry includes additional address information known as tag. The tag contains enough addressing information to fully disambiguate which of the main memory blocks is currently held by that entry.
As an example, if the cache entry is selected by the least significant N bits of a main memory block address, then 2.sup.M-N main memory blocks would map to each cache entry. A tag consisting of the most significant M-N main memory address bits would be sufficient to distinguish which memory block the cache entry contains.
When a CPU accesses a particular main memory location it will first attempt to find the data to be accessed in the cache. The system uses a portion of the main memory address to address the cache and retrieve the cache data and its associated tag. The remaining portion of the main memory address is compared with the tag to determine whether the block in cache corresponds to the desired main memory block. If so, the data can be returned to the CPU. Otherwise, the full main memory address must be used to retrieve the data from the main memory.
There are many conventions for mapping main memory into cache memory and techniques for refilling the cache in the case of cache misses which are well-known in the art. These conventions and techniques are generally described in the book by R. Matick entitled Computer Storage Systems & Technology, John Wiley & Sons, 1977, which is hereby incorporated by reference.
In some systems it is desirable to reserve a portion of the high speed memory usually used as cache memory for other purposes such as storage of microcode or a cache of page table translations. Accordingly, some of the storage space of the high speed memory accessed by the least significant N bits of the generated main memory address will access storage locations that do not store main memory data. Additionally, the unreserved part of the high speed memory used as cache memory will have 2.sup.N -R=L cache entries, where R is the number of cache entries reserved for other use and L is not generally equal to a power of 2. If L is not a power of 2 then it is not possible for any Z bit binary address to have a one to one correspondence between the 2.sup.Z possible addresses and the L cache entries.